#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct NODE
{
	int i;
	struct NODE *next;
}Node,List;

Node *CreateNode(int t)
{
	Node *a;
	a=malloc(sizeof(Node));
	a->next=NULL;
	a->i=t;
	return a;
}//创造一个关键码为t的节点

void Insert(List *a,Node *b)
{
	Node *t=a;
	while(t->next !=NULL)
		t=t->next;
	t->next=b;
}//把节点b插入到链表a的末端

int Search(List *a,int i)
{
	while(a->next!=NULL)
	{
		if((a->next)->i==i)
		return 1;
		a=a->next;
	}
	return 0;
}//搜索节点a的相邻节点i，搜索到返回1，否则返回0；

void set(int *s,int i)
{
	s[i>>5]|=(1<<(i&0x1F));
}

int test(int *s,int i)
{
	return  s[i>>5]&(1<<(i&0x1F));
}

int Length(List l[],int a,int b,int n)
{
	if(a==b) return 0;
	int i,k,temp;
	Node  *tk;
	int *t=malloc(sizeof(int)*n);
	int *s=malloc(sizeof(int)*(n/32+1));
	int *sk1=malloc(sizeof(int)*(n/32+1));
	int *sk2=malloc(sizeof(int)*(n/32+1));
	for(i=0;i<n;i++)
		t[i]=1000000;
	t[a]=0;
		
	for(i=0;i<(n/32+1);i++)
	{
		s[i]=0;
		sk1[i]=0;
		sk2[i]=0;
	}
	
	set(s,a);
	set(sk1,a);
	k=0;
	
	do
	{
		k++;
		for(i=0;i<(n/32+1);i++) sk2[i]=0;//清空sk2。
		for(i=0;i<n;i++)
		{
			if(test(sk1,i))//i在sk1中
			{
				tk=&l[i];//考虑sk1的邻接点
				while(tk->next!=NULL)
				{
					temp=(tk->next)->i;
					if(!test(s,temp))//检测邻接点是否在s中，如果不再，可以加入到sk2。
						set(sk2,temp);//加入到sk2。
					tk=tk->next;
				}
			}
		}
		
		for(i=0;i<n;i++)
		{
			if(test(sk2,i))
			{
				set(s,i);
				t[i]=k;
				if(i==b) 
				{
					int tt=t[i];
					if(s) free(s);
					if(sk1) free(sk1);
					if(sk2) free(sk2);
					if(t) free(t); 
					return tt;
				}
			}
		}	
		
		for(i=0;i<(n/32+1);i++) sk1[i]=0;//清空sk1。
		for(i=0;i<n;i++)
			if(test(sk2,i))  
			{
				set(sk1,i);
			}//把sk2传到sk1中。
	}while(all(s,n)<n);

		if(s) free(s);
		if(sk1) free(sk1);
		if(sk2) free(sk2);
		if(t) free(t); 
	return -1;
}

int all(int s[],int n)
{
	int i,t,a=0;
	for(i=0;i<n;i++)
	{
		if(test(s,i)) t=1; 
		else t=0;
		a+=t;
	}
	return a;
}
